package com.zyk.grate_offer.class07;

import java.util.Arrays;
import java.util.HashSet;

/**
 * 给定一个字符串,和一个字符串数组. 求这个字符串数组拼成字符串的方法数. 字符串可以无限使用
 *
 * @author zhangsan
 * @date 2021/5/15 18:34
 */
public class Code_WorkBreak {

    // 暴力尝试, 通过set
    public static int ways1(String str, String[] strs) {
        HashSet<String> set = new HashSet<>(Arrays.asList(strs));
        return process1(str, 0, set);
    }

    private static int process1(String str, int i, HashSet<String> set) {
        if (i == str.length())
            return 1;
        int ways = 0;
        for (int end = i; end < str.length(); end++) {  // 还是拼接了前边所有能拼接的方法, 都去set里查一下, 这个动作其实就O(N)了
            String pre = str.substring(i, end + 1);     // [)   左闭右开
            if (set.contains(pre)) {
                ways += process1(str, end + 1, set);
            }
        }
        return ways;
    }

    // 尝试1改动态规划
    public static int ways2(String str, String[] strs) {
        int N = str.length();
        HashSet<String> set = new HashSet<>(Arrays.asList(strs));
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            int ways = 0;
            for (int end = i; end < N; end++) {
                String pre = str.substring(i, end + 1);     // [)   左闭右开
                if (set.contains(pre)) {
                    ways += dp[end + 1];
                }
            }
            dp[i] = ways;
        }
        return dp[0];
    }

    // 暴力尝试2: 通过构建前缀树优化
    public static int ways3(String str, String[] strs) {
        // 把strs, 加入到前缀树中
        Node root = new Node();
        for (String s : strs) {
            char[] S = s.toCharArray();
            Node cur = root;
            int path;
            for (char c : S) {
                path = c - 'a';
                if (cur.next[path] == null)
                    cur.next[path] = new Node();
                cur = cur.next[path];
            }
            cur.end = true;
        }
        return process3(str.toCharArray(), 0, root);
    }

    private static int process3(char[] str, int i, Node root) {
        if (i == str.length)
            return 1;
        int ways = 0;
        Node cur = root;
        int path;
        for (int end = i; end < str.length; end++) {  // 还是拼接了前边所有能拼接的方法, 都去set里查一下, 这个动作其实就O(N)了
            path = str[end] - 'a';
            if (cur.next[path] == null) {
                break;
            }
            cur = cur.next[path];
            if (cur.end) {
                ways += process3(str, end + 1, root);
            }
        }
        return ways;
    }

    public static class Node {
        boolean end;
        Node[] next = new Node[26];
    }

    // 暴力尝试2 -> 动态规划
    public static int ways4(String str, String[] strs) {
        // 把strs, 加入到前缀树中
        Node root = new Node();
        for (String s : strs) {
            char[] S = s.toCharArray();
            Node cur = root;
            int path;
            for (char c : S) {
                path = c - 'a';
                if (cur.next[path] == null)
                    cur.next[path] = new Node();
                cur = cur.next[path];
            }
            cur.end = true;
        }
        int N = str.length();
        int[] dp = new int[N + 1];
        dp[N] = 1;
        for (int i = N - 1; i >= 0; i--) {
            int ways = 0;
            Node cur = root;
            int path;
            for (int end = i; end < N; end++) {  // 还是拼接了前边所有能拼接的方法, 都去set里查一下, 这个动作其实就O(N)了
                path = str.charAt(end) - 'a';
                if (cur.next[path] == null) {
                    break;
                }
                cur = cur.next[path];
                if (cur.end) {
                    ways += dp[end + 1];
                }
            }
            dp[i] = ways;
        }
        return dp[0];
    }


    // for test
    // 以下的逻辑都是为了测试
    public static class RandomSample {
        public String str;
        public String[] arr;

        public RandomSample(String s, String[] a) {
            str = s;
            arr = a;
        }
    }

    // 随机样本产生器
    public static RandomSample generateRandomSample(char[] candidates, int num, int len, int joint) {
        String[] seeds = randomSeeds(candidates, num, len);
        HashSet<String> set = new HashSet<>();
        for (String str : seeds) {
            set.add(str);
        }
        String[] arr = new String[set.size()];
        int index = 0;
        for (String str : set) {
            arr[index++] = str;
        }
        StringBuilder all = new StringBuilder();
        for (int i = 0; i < joint; i++) {
            all.append(arr[(int) (Math.random() * arr.length)]);
        }
        return new RandomSample(all.toString(), arr);
    }

    public static String[] randomSeeds(char[] candidates, int num, int len) {
        String[] arr = new String[(int) (Math.random() * num) + 1];
        for (int i = 0; i < arr.length; i++) {
            char[] str = new char[(int) (Math.random() * len) + 1];
            for (int j = 0; j < str.length; j++) {
                str[j] = candidates[(int) (Math.random() * candidates.length)];
            }
            arr[i] = String.valueOf(str);
        }
        return arr;
    }

    public static void main(String[] args) {
        char[] candidates = { 'a', 'b' };
        int num = 20;
        int len = 4;
        int joint = 5;
        int testTimes = 30000;
        boolean testResult = true;
        for (int i = 0; i < testTimes; i++) {
            RandomSample sample = generateRandomSample(candidates, num, len, joint);
            int ans1 = ways1(sample.str, sample.arr);
            int ans2 = ways2(sample.str, sample.arr);
            int ans3 = ways3(sample.str, sample.arr);
            int ans4 = ways4(sample.str, sample.arr);
            if (ans1 != ans2 || ans3 != ans4 || ans2 != ans4) {
                testResult = false;
            }
        }
        System.out.println(testTimes + "次随机测试是否通过：" + testResult);
    }

}
